package a.codetop;

import 其他.DataStructure.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class 栈版_前中后序 {
    public List<Integer> 前序(TreeNode root) {
        List<Integer> res=new ArrayList<>(); if(root==null)return res;
        //
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        //
        while(!stack.isEmpty()){
            //1弹
            TreeNode top = stack.pop();
            //2pt
            res.add(top.val);
            //3ifPush
            if(top.right!=null)stack.push(top.right);
            if(top.left!=null)stack.push(top.left);
        }
        //
        return res;
    }

    public List<Integer> 中序(TreeNode root) {
        List<Integer> res=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode>();
        //
        while(stack.size()>0 || root!=null) {
            //不断往左子树方向走，每走一次就将当前节点暂存到栈中
            if(root!=null) { stack.add(root); root=root.left; }
            //当前节点为空，说明左边走到头了，从栈中弹出节点并pt,之后右一
            else {
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                //右一
                root = tmp.right;
            }
        }
        //
        return res;
    }
}


